package chapter03;

public class MaxPathSum124 {
    /**
     * 递归搜索
     * process(x) 以x为根节点的最大路径和
     * 必须左子树和右子树必须全部大于0才计入以x为根节点的路径中
     * 因此需要一个全局变量length更新最大的路径和
     * 递归出口
     * 1).x==null
     *  return 0;
     * 2).x!=null
     *  leftNode=Math.max(process(x.left),0)  左子树最大路径和
     *  rightNode=Math.max(process(x.right),0) 右子树最大路径和
     *  length=Math.max(length,x.val+leftNode+rightNode)  更新length
     *  return x.val+(leftNode>rightNode?leftNode:rightNode) 返回以x为根节点的最大路径和
     */
    public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
    }

    int length;
    public int maxPathSum(TreeNode root) {
        if(root==null){
            return 0;
        }
        length=Integer.MIN_VALUE;
        process(root);
        return length;
    }

    public int process(TreeNode x){
        if(x==null){
            return 0;
        }
        int leftNode=Math.max(process(x.left),0);
        int rightNode=Math.max(process(x.right),0);
        length=Math.max(length,x.val+leftNode+rightNode);
        return x.val+(leftNode>rightNode?leftNode:rightNode);
    }
}
